package com.wangwei.sort;

import edu.princeton.cs.algs4.StdOut;

public class Merge extends Example{

    @Override
    public void sort(Comparable[] arr) {
        Comparable[] aux = new Comparable[arr.length];
        sort(arr, aux, 0, arr.length-1);
        assert isSorted(arr);
    }

    private void sort(Comparable[] arr, Comparable[] aux, int lo, int hi) {
        if (hi <= lo) return;
        int mid = lo + (hi - lo) / 2;
        sort(arr, aux, lo, mid);
        sort(arr, aux, mid + 1, hi);
        merge(arr, aux, lo, mid, hi);
    }

    protected void merge(Comparable[] arr, Comparable[] aux, int lo, int mid, int hi) {


        assert isSorted(arr, lo, mid);
        assert isSorted(arr, mid+1, hi);


        //先把数据复制到临时的数组中
        for (int k = lo; k <= hi; k++) {
            aux[k] = arr[k];
        }

        //再重新给主数组添加元素
        int i = lo, j = mid+1;
        for (int k = lo; k <= hi; k++) {
            if      (i > mid)              arr[k] = aux [j++];// 左半边用尽，取右半边。
            else if (j > hi)               arr[k] = aux[i++];// 右半边用尽，取左半边。
            else if (less(aux[j], aux[i])) arr[k] = aux[j++];// 右半边的当前元素小于左半边的当前元素，取右半边的当前元素
            else                           arr[k] = aux[i++];// 左半边的当前元素小于右半边的当前元素，取左半边的当前元素
        }

        assert isSorted(arr, lo, hi);

    }

    private boolean isSorted(Comparable[] arr,int lo ,int hi) {
        for (int i = lo; i < hi; i++)
            if (less(arr[i++], arr[i])) return false;
        return true;
    }

    public static void main(String[] args) {
        String [] arr = {"A","S","D","F","G","H","J","K","L"};
        Example example = new Merge();

        example.sort(arr);
        assert example.isSorted(arr);
        example.show(arr);
    }
}
